Leetcode 198.打家劫舍

题目描述：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

1
2
3
4

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

1
2
3
4

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

链接：

https://leetcode-cn.com/problems/house-robber

题目分析

  很容易就看出这是一道经典的动态规划题目。我们使用 dp[i] 表示能够从前 i 间房屋获取最高金额的现金。则对于第 i 间房屋，我们有两种选择。

• 偷。则需要保证的是我们不能偷第 i-1 间房屋（不能偷相邻两间房屋）。因此能够获取的最大金额是 dp[i-2] + nums[i-1]。（第 i 间房屋是 nums[i-1]）
• 不偷。则我们能够获取的最大金额就是 dp[i-1]。

  这样我们便得到了我们的动态转移公式 dp[i] = max(dp[i-2] + nums[i-1], dp[i-1])。而边界条件是 dp[0] = 0，dp[1] = nums[0]。可以注意到的是，每个状态只跟前两个状态有关，并且我们最后的结果就是 dp[nums.size()]，也即动态规划的最后一个状态。则我们可以使用滚动数组的思想，丢弃前面的状态，只用三个变量分别存储当前的状态 money、前一个状态 one、前两个状态 two。

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int rob(vector<int>& nums) {
        int two = 0, one = 0, money = 0;
        for(int num : nums){
            money = max(two + num, one);
            two = one;
            one = money;
        }
        return money;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是数组的大小。我们只需要对数组进行一次遍历。
  空间复杂度：$O(1)$。经过优化之后我们只需要常数个变量的空间。